package leetCode;

import java.util.Stack;

public class Node {
    Node next;
}
/*
   二叉树
    */
class TwoTree{
    int value;
    TwoTree left;
    TwoTree right;
}
class Tree{
    //先序遍历
    public static void First(TwoTree t){
        if(t==null){
            return;
        }
        System.out.print(t.value+" ");
            First(t.left);
            First(t.right);
    }
    //中序遍历
    public static void Mid(TwoTree t){
        if(t==null){
            return;
        }
        Mid(t.left);
        System.out.print(t.value+" ");
        Mid(t.right);
    }
    //后序遍历
    public static void After(TwoTree t){
        if(t == null)
            return;
        After(t.left);
        After(t.right);
        System.out.print(t.value+" ");
    }
    /*
    非递归实现
     */

    //先序
    /*
    先把头节点压入栈，弹出，让后先左后右
     */
    public static void Pre(TwoTree t){
        if(t!=null){
            Stack<TwoTree> stack = new Stack<>();
            stack.add(t);
            while(!stack.isEmpty()){
                t = stack.pop();
                System.out.print(t.value+" ");
                if(t.right!=null){
                    stack.push(t.right);
                }
                if(t.left!=null){
                    stack.push(t.left);
                }
            }
        }
    }
    //后序
    /*
    按头，弹出到收集栈，左右的方式压入栈，
         */
    public static void Pos(TwoTree t){
        if(t!=null){
            Stack<TwoTree> s1 = new Stack<>();
            Stack<TwoTree> s2 = new Stack<>();
           s1.push(t);
           while(!s1.isEmpty()){
               t=s1.pop();
               s2.push(t);
               if(t.left!=null)
                   s1.push(t.left);
               if(t.right!=null)
                   s1.push(t.right);
           }
           while(!s2.isEmpty()){
               System.out.print(s2.pop().value+" ");
           }
        }
        System.out.print(" ");
    }
    //中序
    /*
    树左边界进栈，依次弹的过程打印，对弹出的右·节点数周而复始
     */
    public static void In(TwoTree t){
        if(t!=null){
            Stack<TwoTree> s = new Stack<>();
            while(!s.isEmpty()||t!=null){
                if(t!=null){
                    s.push(t);
                    t=t.left;
                }else{
                    t = s.pop();
                    System.out.print(t.value+" ");
                    t=t.right;
                }
            }
        }
    }
}
class Link{
    /*
 寻找链表是否有环，返回环的第一个结点
 */
    public static Node findRing(Node head){
        Node n1 = head.next;//慢指针
        Node n2 = head.next.next;//快指针;
        while(n1!=n2){
            if(n2.next==null||n2.next.next==null)
                return null;
            n1=n1.next;
            n2=n2.next.next;
        }
        n2 = head;
        while(n1!=n2){
            n1=n1.next;
            n2=n2.next;
        }
        return n1;
    }
    /*
    判断两个链表是否相交
     */
    public static Node findSamePoint(Node head1,Node head2){
        if(head1==null||head2==null)
            return null;
        int n=0;
        Node n1 = head1.next;
        Node n2 = head2.next;
        while(n1.next!=null) {
            n++;
            n1 = n1.next;
        }
        while(n2.next!=null) {
            n--;
            n2 = n2.next;
        }
        n1 = n>0?head1:head2;
        n2 = n1 == head1?head2:head1;
        n = Math.abs(n);
        while(n!=0){
            n--;
            n1 = n1.next;
        }
        while(n1!=n2){
            n1= n1.next;
            n2=n2.next;
        }
        return n1;
    }
    /*
    找两个有环链表是否相交
     */
    public static Node bothLoop(Node head1,Node loop1,Node head2,Node loop2){
        Node cur1 = null;
        Node cur2 = null;
        if(loop1==loop2){
            cur1= head1;
            cur2 = head2;
            int n=0;
            while(cur1!=loop1){
                n++;
                cur1= cur1.next;
            }
            while(cur2!=loop2){
                n--;
                cur2=cur2.next;
            }
            cur1 = n>0?head1:head2;
            cur2 = head1==cur1?head2:head1;
            n = Math.abs(n);
            while(n!=0){
                n--;
                cur1= cur1.next;
            }
            while(cur1!=cur2){
                cur1=cur1.next;
                cur2=cur2.next;
            }
            return cur1;
        }else{
            cur1 = loop1.next;
            while(cur1!=loop1){
                cur1=cur1.next;
                if(cur1==loop2)
                    return cur1;
            }
            return null;
        }
    }

}

